package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] keys = new int[]{97, 82, 75, 53, 17, 61, 70, 12, 61, 58, 26};
        System.out.print("关键字序列：");
        System.out.println(Arrays.toString(keys));
        mergeSort.mergeSort(keys);
    }

    // 归并排序
    public void mergeSort(int[] X) {
        System.out.println("归并排序（升序）");
        // 将X中若干相邻子序列归并， 子序列长度: 1，2，4..
        for (int n = 1; n < X.length; n *= 2) {
            mergePass(X, n);
        }
    }

    //一趟归并，将X中若干相邻子序列两两归并，子序列长度为n
    private void mergePass(int[] X, int n) {
        System.out.print("子序列长度n=" + n + "  ");
        int[] Y = new int[X.length];
        for (int i = 0; i < X.length; i += 2 * n)                //将X中若干相邻子序列归并到Y中
            merge(X, Y, i, i + n, n);                        //一次归并

        // Y数组的值copy回X
        System.arraycopy(Y, 0, X, 0, X.length);

        System.out.println(Arrays.toString(X));
    }

    //一次归并（升序）
    //将X中分别以begin1、begin2开始的两个相邻子序列归并（升序），子序列长度为n
    private void merge(int[] X, int[] Y, int begin1, int begin2, int n) {

        int i = begin1, j = begin2, k = begin1;
        while (i < begin1 + n && j < begin2 + n && j < X.length)     //将X中两个相邻子序列归并到Y中
            if (X[i] < X[j])                                         //（升序）将较小值复制到Y中
                Y[k++] = X[i++];
            else
                Y[k++] = X[j++];

        while (i < begin1 + n && i < X.length)                   //将前一个子序列剩余元素复制到Y中，子序列长度可能不足n
            Y[k++] = X[i++];
        while (j < begin2 + n && j < X.length)                   //将后一个子序列剩余元素复制到Y中
            Y[k++] = X[j++];
    }
}
